package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description: 困难(☆)
 * 个人觉得这道题目比较难！
 * 需要思考的地方有两点：
 * 1. 怎么找到最大值的最小
 * 2. 如何分割k个连续子数组
 * 根据分析，思路如下：
 * 首先，最坏的情况是，分割的子数组就是原数组，那么此时子数组各自和，就是数组所有元素之和
 * 最好的情况是，分割的子数组中，只有一个值，而这个值就是数组中的最大元素，
 * 这样就可以得到一个分割子数组之后最大值之和的区间[max(nums), sum(nums)]
 *
 * 那我们要做的就是在这个区间内找到某个值，而这个值可以满足，数组之和的最大值不能大于这个元素的个数split。
 * 如果split>m(分割数组个数)，则表示划分的子数组多了，也就是这个元素太小了，所以区间就变成[mid + 1, right]
 *
 * 如果split<m(分割数组个数)，则表示划分的子数组多了，也就是这个元素太大了，所以区间就变成[left, mid]
 * @author: YuKai Fan
 * @create: 2024/8/17 21:29
 **/
public class 分割数组的最大值 {

    public static void main(String[] args) {
        分割数组的最大值 o = new 分割数组的最大值();
        int[] nums = {1,2,3,4,5};
        int k = 5;
        System.out.println(o.splitArray(nums, k));
    }

    /**
     * 给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
     *
     * 设计一个算法使得这 k 个子数组各自和的最大值最小。
     *
     * 输入：nums = [7,2,5,10,8], k = 2
     * 输出：18
     * 解释：
     * 一共有四种方法将 nums 分割为 2 个子数组。
     * 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
     * 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小
     *
     * 输入：nums = [1,2,3,4,5], k = 2
     * 输出：9
     *
     * 输入：nums = [1,4,4], k = 3
     * 输出：4
     * @param nums
     * @param k
     * @return
     */
    public int splitArray(int[] nums, int k) {
        int max = 0, sum = 0;
        for (int num : nums) {
            max = Math.max(max, num);
            sum += num;
        }
        int left = max;
        int right = sum;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (split(nums, mid) > k) {
                // 这里就表示分割的数组数量太多了，即mid值太小了，所有区间就是[mid + 1, right]
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    /**
     * 这里需要计算当前需要分割的子数组数量
     * @param nums
     * @param mid
     * @return
     */
    private int split(int[] nums, int mid) {
        // 分割数最小为1
        int split = 1;
        // 当前区间的元素之和
        int curSum = 0;
        for (int num : nums) {
            // 尝试加上当前遍历的这个数，如果加上去超过了「子数组各自的和的最大值」，就不加这个数，另起炉灶
            if (curSum + num > mid) {
                // 这里为什么要跳过这个数呢
                // 因为此时已经找到了一个满足条件的分割点，大于最大值，所以直接跳过这个数
                curSum = 0;
                split++;
            }
            curSum += num;
        }
        return split;
    }
}
